This invention generally relates to computer programming languages, and more particularly to computer programming languages with dynamic linking that verify instructions while supporting lazy loading.
In general, computer programs are written as source code statements in a high level language which is easy for a human being to understand. As the computer programs are actually executed, a computer responds to machine code, which consists of instructions comprised of binary signals that directly control the operation of a central processing unit (CPU). It is well known in the art to use a special program called a compiler to read the source code and to convert its statements into the machine code instructions of the specific CPU. The machine code instructions thus produced are platform dependent, that is, different computer devices have different CPUs with different instruction sets indicated by different machine codes.
It is also known in the art to construct more powerful programs by combining several simpler programs. This combination can be made by copying segments of source code together before compiling and then compiling the combined source. When a segment of source code statements is frequently used without changes it is often preferable to compile it once, by itself, to produce a module, and to combine the module with other modules only when that functionality is actually needed. This combining of modules after compilation is called linking. When the decision on which modules to combine depends on run time conditions and the combination of the modules happens at run time, just before execution, the linking is called dynamic linking.
An advantage of linking is that programs can be developed a module at a time and productivity can be enhanced as different developers work, possibly at different sites, simultaneously on separate modules.
An advantage of linking performed at run time, that is, dynamic linking when the program is being executed, is that modules not used during execution need not be linked, thus reducing the number of operations that must be executed and likely reducing the size of the executing code. In general, modules have to be loaded, that is identified and brought into memory, before being linked. The deferred linking of modules until the module is needed allows a deferral in loading those modules as well, which is called lazy loading.
It is prudent, when assembling several modules that may have been written independently, to check both that each module performs properly within its own four corners, i.e., with intra-module checks, and also that the modules work properly together, i.e. with inter-module checks. By analogy with the terminology used by the designers of the JAVA(trademark) programming language, this post compilation module checking can be called verification.
An example of a computer architecture that benefits from dynamic linking is a virtual machine (VM) such as the JAVA(trademark) virtual machine (JVM) of Sun Microsystems, Inc., which is an abstract computer architecture that can be implemented in hardware or software. Either implementation is intended to be included in the following descriptions of a VM.
A VM can provide platform independence in the following manner. Statements expressed in a high level computing language, such as the JAVA(trademark) programming language, are compiled into VM instructions that are system independent. The VM instructions are to the VM what machine code is to a central processing unit (CPU). The VM instructions can then be transferred from one machine to another. Each different processor needs its own implementation of a VM. The VM runs the VM instructions by translating or interpreting the VM instructions one or more instructions at a time. In many implementations, the VM
The process of programming using such a VM then has two time epochs associated with it; xe2x80x9ccompile timexe2x80x9d refers to the steps which convert the high level language into the VM instructions, and xe2x80x9crun timexe2x80x9d refers to the steps which in a JAVA(trademark) VM environment, interpret instructions to execute the module. Between compile time and run time, the modules of instructions compiled from statements can reside dormant for extended, arbitrary periods of time, or can be transferred from one storage device to another, including being transferred across a network.
The problems encountered in trying to implement dynamic linking with verification and with or without lazy loading can be illustrated for the example of the JAVA(trademark) virtual machine. The JVM is a particular VM for the object oriented JAVA(trademark) high level programming language that is designed to perform dynamic linking, verification and lazy loading as described for the conventional JVM in The JAVA(trademark) Virtual Machine Specification, by T. Lindholm and Frank Yellin, Addison-Wesley, Menlo Park, Calif. 1997.
Object oriented programming techniques such as those used by the JAVA(trademark) platorm are widely used. The basic unit of object oriented programs is the object which has methods (procedures) and fields (data), herein called members. Objects that share members are grouped into classes. A class defines the shared members of the objects in the class. Each object then is a particular instance of the class to which it belongs. In practice, a class is often used as a template to create multiple objects (multiple instances) with similar features.
One property of classes is encapsulation, which describes the property that the actual implementation of the members within the class are hidden from an outside user, and other classes, except as exposed by an interface. This makes classes suitable for distributed development, for example by different developers at different sites on a network. A complete program can be formed by assembling the classes that are needed, linking them together, and executing the resulting program.
Classes enjoy the property of inheritance. Inheritance is a mechanism that enables one class to inherit all of the members of another class. The class that inherits from another class is called a subclass; the class that provides the attributes is the superclass. Symbolically, this can be written as subclass less than =superclass, or superclass= greater than subclass. The subclass can extend the capabilities of the superclass by adding additional members. The subclass can override an attribute of the superclass by providing a substitute member with the same name and type.
The JVM operates on a particular binary format for the compiled classesxe2x80x94the class file format. A class file contains JVM instructions and a symbol table, as well as other ancillary information. For the sake of security, the JVM imposes strong format and structural constraints on the instructions in a class file. In particular example, JVM instructions are type specific, intended to operate on operands that are of a given type as explained below. Similar constraints could be imposed by any VM. Any language with functionality that can be expressed in terms of a valid class file can be hosted by the JVM. The class file is designed to handle object oriented structures that can represent programs written in the JAVA(trademark) programming language, but may also support several other programming languages.
In the class file, a variable is a storage location that has associated a type, sometimes called its compile-time type, that is either a primitive type or a reference type. The reference types are pointers to objects or a special null reference which refers to no object. The type of a subclass is said to be a subtype of its superclass. The primitive types for the JVM include boolean (taking the truth values true and false), char (code for a Unicode character), byte (signed eight bits of 0 or 1), short (signed short integer), int (signed integer), long (signed long ,integer), float (single-precision floating point number) or double (double precision floating point number).
The members of a class type are fields and methods; these include members inherited from the superclass. The class file also names the superclass. A member can be public, which means that it can be accessed by members of any class. A private member may be accessed only by members of the class that contains its declaration. A protected member may be accessed by members of the declaring class or from anywhere in the package in which it is declared. In the JAVA(trademark) programming language, classes can be grouped and the group can be named; the named group of classes is a package.
The actual instructions for the JVM are contained within methods of the class ,encoded by the class file.
When a JAVA(trademark) language program violates constraints of an operation, the JVM detects an invalid condition and signals this error to the program as an exception. An exception is said to be thrown from the point where it occurred and it is said to be caught at the point to which control is transferred. Every exception is represented by an instance of the class Throwable or one of its subclasses; such an object can be used to carry information from the point at which an exception occur s to part of the program, an exception handler, that catches it and deals with it.
The JVM starts execution by invoking the method xe2x80x9cmainxe2x80x9d of some specified class, passing it a single argument which is an array of strings. This causes the specified class to be loaded, linked and initialized.
Loading refers to the process of finding the binary form of a class or package with a particular name, typically by retrieving a binary representation previously compiled from source code. In the JVM, the loading step retrieves the class file representing the desired class. The loading process is implemented by the bootstrap class loader or a user defined class loader. A user-defined class loader is itself defined by a class. A class loader may indicate a particular sequence of locations to search in order to find the class file representing a named class. A class loader may cache binary representations of classes, pre-fetching based on expected usage, or load a group of related classes together. The more classes that are pre-fetched or group loaded the more xe2x80x9ceagerxe2x80x9d is the loader. A xe2x80x9clazyxe2x80x9d loader pre-fetches or groups as few classes as possible. The conventional JVM specification permits a broad spectrum of loading behaviors between eager and almost fully lazy.
A VM is fully lazy if it calls a class loader to load a class only at the time that the class is first necessary to execute an instruction of a class currently being processed. Fully lazy loading, if achieved, does not waste run time resources, such as system memory and execution time, loading classes that are not strictly required at run time.
Linking in the JVM is the process of taking a binary form of a class in memory and combining it into the run time state of a VM, so that it can be executed. A class must be loaded before it can be linked. Three different activities are involved in linking according to the JVM spec: verification, preparation and resolution of symbolic references.
During verification, necessary constraints on a binary class in the class file format are checked. Doing so is fundamental to the security provisions of the JVM. Verification ensures that illegal operations are not attempted by the JVM that can lead to meaningless results or that can compromise the integrity of the operating system, the file system, or the JVM itself. However, checking these constraints sometimes requires knowledge of subtyping relations among other classes; so successful verification typically depends on the properties of other classes referenced by the class being verified. This has the effect of making the current JVM design specification for verification context sensitive.
The binary classes of the JVM are essentially exemplars of general program modules that contain instructions produced from compiled source statements. Context sensitivity of validity checks means that those checks depend on information spread across more than one module, i.e., those checks are called cross-module checks or inter-module checks herein. Validity checks that do not require information from another module are called intra-module checks herein.
Context sensitive verification has some disadvantages. For example in an object oriented programming system like the JAVA(trademark) platform, it leads to a verifier initiating class loading when the verifier needs to check subtype relations among classes not already loaded. Such loading can occur even if the code referencing the other classes is not ever executed. That is, context sensitive verification can interfere with fully lazy loading. Because of this, loading can consume memory and slow execution at run time compared to a process that does not load the classes unless they are referenced by the instructions that are actually executed.
When verification is context sensitive there is also no provision for verifying one class or module at a time before run time. This is a disadvantage because classes cannot be verified ahead of time, e.g. before run time, so verification must incur a run time cost. Thus there is a need for module-by-module, also called module-at-a-time, verification before run time. Such verification is herein called pre-verification because technically it is distinct from the verification which occurs during run time linking by the JVM.
Also, since verification is performed at run time, a class that has been run once, and passed verification, is subjected to verification again each time the class is loadedxe2x80x94even if the class is being used in the same application on the same host computer, where no new verification issues are likely or where a situation can be arranged such that no changes that would affect verification can be made. This can lead to redundant verification, thereby requiring more memory and executing more slowly during run time than ought to be necessary. Thus there is a need for an option to use pre-verified modules without further, or with minimum, verification at run time.
The needs for pre-verification and fully lazy loading are separate needs that might be met separately. There is also a need for supporting module-by-module pre-verification along with fully lazy loading.
The need for pre-verification, including reduction of run time verification, may conflict with the goals of security that require all modules supplied to a virtual machine or any computing architecture be checked at run time to prevent illegal or damaging operations. For example, in an untrusted situation, such as downloading a module and its pre-verification output from the Internet, an attacker may be able to spoof the pre-verification outputxe2x80x94possibly making a malignant class appear benign. Thus, there is a need for pre-verification that is usable in untrusted situations, as in downloading modules across the Internet.
The need for fully lazy loading or module-by-module pre-verification engenders a need for a substitute representation of a type lattice. A type lattice is a mathematical structure expressing subtyping relationships among types. A representation of a type lattice is built by the JVM for indicating the types and subtypes of classes during run time. The JVM also maintains references and types of all the attributes of the classes that are being linked. Similar run time structures are expected to be useful for any dynamic linking process. To support class-by-class pre-verification or fully lazy loading, type checking must be done without full knowledge of the type lattice, most of which is typically defined in other modules which may not yet otherwise need to be loaded. In particular, the JVM typically needs to find a LUB (lowest upper bound) type in the type lattice during verification. Thus, there is a need to perform the functions that rely on a LUB even when the type lattice is unavailable.
The foregoing and other features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.
It is an object of the invention to support verification during linking while providing for fully lazy loading. It would be advantageous for a dynamic linker, and in particular the JVM, to require that all resolution of referenced modules (e.g. classes) would be done lazily at specific, defined points during execution of instructions (e.g., of a method). The advantages include:
Write once, run anywhere (WORA) characteristics are improved. The behavior of a program with respect to linkage errors is the same on all platforms and implementations.
Testability is greatly improved. For example, one need not anticipate all the places where a class or method might be linked and attempt to catch exceptions at all those places in case the class or method cannot be found.
Users can determine the presence of modules in a reliable and simple way. For example, the user can avoid linkage errors due to calls to modules missing on a different version of a run time environment by placing those references on a program branch that is not executed unless the different version is available.
The breadth of loading behaviors of the conventional JVM specification does not permit these advantages.
It is another object of the present invention to support one-module-at-a-time pre-verification. It is also an object of the present invention to utilize pre-verified instructions to reduce run time verification. Some users of the JAVA(trademark) platform would want to perform context insensitive, or context independent, verification checks on some classes. There are a number of advantages to context independent checking which can be performed during or after compilation and before run time. The advantages include:
Some verification errors can be detected before run time;
The linking component of run time if one is still required, is smaller and simpler because the amount of verification code it contains is reduced; and
The user can store modules (in a secured repository, for example, a RDBMS (relational database management system) on a module-by-module basis rather than application by application, and do as much work as possible before of run time. This obviates redundant verification and reduces or eliminates run time costs of verification.
It is another object of the present invention to support one-module (or class)-at-a-time pre-verification with run time verification that permits fully lazy loading, in order to enjoy the benefits of both at the same time.
It is another object of the present invention to pre-verify modules from untrusted sources, to increase the scope of situations in which the benefits of pre-verification apply.
It is another object of the present invention to utilize a substitute for a LUB when full knowledge of the type lattice is lacking to simplify inter-module validity checks.
These and other objects and advantages of the present invention are provided by a method, computer program, signal transmission and apparatus for trusted verification of instructions in a module of a computer program, one-module-at-a-time. It is determined whether checking an instruction in a first module requires information in a referenced module different than the first module. If such information is required, a constraint for the referenced module is written without requiring access to the referenced module and the written constraint is digitally signed.
In another aspect of the invention, a method, computer program, signal transmission and apparatus provides trusted verification of instructions in a module of a computer program. It is determined whether a suspect module to be loaded is stored in an untrusted storage location. If from an untrusted source, the suspect module is loaded and one-module-at-a-time pre-verification is performed on the suspect module before linking. If the suspect module passes such pre-verification, the module is stored in a trusted cache.
In another aspect of the invention, a method, computer program, signal transmission and apparatus provides trusted verification of instructions in a module of a computer program during linking. It is determined whether a first module has passed pre-verification one-module-at-a-time. If the first module has passed pre-verification, it is determining whether results are trusted. If the results are trusted, a pre-verification constraint on a constrained module, if any, is read. If any pre-verification constraint is read, it is determined if the constrained module is loaded. If the constrained module is loaded, the pre-verification constraint is enforced.
In another aspect of the invention, a trusted pre-verification system performs trusted verification one-module-at-a-time before linking with reduced verification during linking. The system includes a network and a computer readable storage medium connected to the network for storing a module of a computer program. A trusted cache is connected to the network for storing modules and constraints under the control of a single processor. A memory into which a module is loaded is connected to the network. A processor connected to the network is configured to determine whether a suspect module to be loaded is stored in an untrusted storage location, and, if so, to load the suspect module and perform one-module-at-a-time pre-verification on the suspect module before linking. The module is then stored in the trusted cache if the suspect module passes such verification. The same or a different trusted processor connected to the network is configured to perform one-module-at-a-time pre-verification. It is determined whether checking an instruction in the suspect module requires information in a referenced module different than the suspect module. If so, a constraint for the referenced module is written in the trusted cache, without requiring access to the referenced module. The same or a different trusted processor connected to the network is configured to determine whether a first module has passed pre-verification one-module-at-a-time before linking, and to determine whether results are trusted if the first module has passed pre-verification. A pre-verification constraint on a constrained module, if any, is read if the results are trusted. If any pre-verification constraint is read, and if the constrained module is loaded, the pre-verification constraint is enforced.